#include "genetic_algorithm.h"
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <limits>
#include <QDebug>
#include <random>

// 定义无穷大的值，用于表示无法达到的距离
const double INF = std::numeric_limits<double>::max();

// 构造函数，初始化遗传算法参数和城市数量
GeneticAlgorithm::GeneticAlgorithm(const QVector<QVector<double>> &distanceMatrix, int populationSize, int generations, double mutationRate)
    : distanceMatrix(distanceMatrix), populationSize(populationSize), generations(generations), mutationRate(mutationRate) {
    numberOfCities = distanceMatrix.size();
    srand(static_cast<unsigned>(time(0)));  // 初始化随机数生成器
}

// 设置种群大小
void GeneticAlgorithm::setPopulationSize(int size) {
    populationSize = size;
}

// 获取当前种群大小
int GeneticAlgorithm::getPopulationSize() const {
    return populationSize;
}

// 设置遗传算法的代数
void GeneticAlgorithm::setGenerations(int gens) {
    generations = gens;
}

// 获取遗传算法的代数
int GeneticAlgorithm::getGenerations() const {
    return generations;
}

// 设置变异率
void GeneticAlgorithm::setMutationRate(double rate) {
    mutationRate = rate;
}

// 获取变异率
double GeneticAlgorithm::getMutationRate() const {
    return mutationRate;
}

// 创建一个随机个体，即一个随机的路径
Individual GeneticAlgorithm::createRandomIndividual() {
    Individual individual;
    individual.path.resize(numberOfCities);  // 设置个体的路径长度为城市数量
    std::random_device rd;
    std::mt19937 rng(rd());

    std::iota(individual.path.begin(), individual.path.end(), 0);  // 生成城市的初始序列
    std::shuffle(individual.path.begin(), individual.path.end(), rng);  // 随机打乱城市序列

    return individual;
}

// 评估个体的适应度，适应度是路径的倒数（路径越短适应度越高）
void GeneticAlgorithm::evaluateFitness(Individual &individual) {
    double totalDistance = 0.0;

    for (int i = 0; i < numberOfCities - 1; ++i) {
        double distance = distanceMatrix[individual.path[i]][individual.path[i + 1]];
        if (distance == 0.0) distance = INF;  // 将0视为无穷大
        totalDistance += distance;
    }
    double lastLeg = distanceMatrix[individual.path[numberOfCities - 1]][individual.path[0]];
    if (lastLeg == 0.0) lastLeg = INF;  // 将最后一段的0视为无穷大
    totalDistance += lastLeg;

    individual.fitness = 1.0 / totalDistance;  // 适应度为路径长度的倒数
}

// 对个体进行变异，即交换路径中的两个城市
void GeneticAlgorithm::mutate(Individual &individual) {
    int index1 = rand() % individual.path.size();
    int index2 = rand() % individual.path.size();
    std::swap(individual.path[index1], individual.path[index2]);  // 交换路径中的两个城市
}

// 执行交叉操作，生成新的后代个体
Individual GeneticAlgorithm::crossover(const Individual &parent1, const Individual &parent2) {
    int size = parent1.path.size();
    Individual offspring;
    offspring.path.resize(size, -1);

    int start = rand() % size;
    int end = rand() % size;

    if (start > end) std::swap(start, end);

    for (int i = start; i <= end; ++i) {
        offspring.path[i] = parent1.path[i];  // 从parent1拷贝一部分路径
    }

    int fillIndex = 0;
    for (int i = 0; i < size; ++i) {
        if (offspring.path[i] == -1) {
            while (std::find(offspring.path.begin(), offspring.path.end(), parent2.path[fillIndex]) != offspring.path.end()) {
                ++fillIndex;
            }
            offspring.path[i] = parent2.path[fillIndex];  // 从parent2填补剩余路径
        }
    }

    return offspring;
}

// 使用轮盘赌选择法选择一个个体作为父代
Individual GeneticAlgorithm::rouletteWheelSelection(const std::vector<Individual> &population) {
    double totalFitness = std::accumulate(population.begin(), population.end(), 0.0,
                                          [](double sum, const Individual &ind) { return sum + ind.fitness; });

    double randomPoint = (rand() / (double)RAND_MAX) * totalFitness;
    double cumulativeSum = 0.0;

    for (const Individual &ind : population) {
        cumulativeSum += ind.fitness;
        if (cumulativeSum >= randomPoint) {
            return ind;
        }
    }

    return population.back();  // 返回最后一个个体以防止计算误差
}

// 运行遗传算法求解旅行商问题
Individual GeneticAlgorithm::solve() {
    std::vector<Individual> population(populationSize);

    for (int i = 0; i < populationSize; ++i) {
        population[i] = createRandomIndividual();  // 初始化种群
        evaluateFitness(population[i]);  // 评估每个个体的适应度
    }

    for (int generation = 0; generation < generations; ++generation) {
        std::sort(population.begin(), population.end(), [](const Individual &a, const Individual &b) {
            return a.fitness > b.fitness;  // 按适应度排序，适应度高的个体排在前面
        });

        // 保留当前最优个体
        Individual bestIndividual = population[0];

        // 生成新一代种群
        std::vector<Individual> newPopulation(populationSize);
        for (int i = 0; i < populationSize; ++i) {
            Individual parent1 = rouletteWheelSelection(population);  // 选择父代
            Individual parent2 = rouletteWheelSelection(population);
            Individual offspring = crossover(parent1, parent2);  // 生成后代

            if (rand() % 100 < mutationRate * 100) {
                mutate(offspring);  // 按照变异率对后代进行变异
            }

            evaluateFitness(offspring);  // 评估新个体的适应度
            newPopulation[i] = offspring;  // 将新个体加入新种群
        }

        // 替换种群并引入精英个体
        newPopulation[0] = bestIndividual;  // 保留当前最优个体
        population = newPopulation;  // 更新种群

        // 输出每一代的最优结果
        qDebug() << "Generation" << generation << "Best distance:" << 1.0 / population[0].fitness;
    }

    return population[0];  // 返回最终最优个体
}
